DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.56

Testing Properties of Distributions in the Streaming Model

Authors: Sampriti Roy and Yadu Vasudev

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

We study distribution testing in the standard access model and the conditional access model when the memory available to the testing algorithm is bounded. In both scenarios, we consider the samples appear in an online fashion. The goal is to test the properties of distribution using an optimal number of samples subject to a memory constraint on how many samples can be stored at a given time. First, we provide a trade-off between the sample complexity and the space complexity for testing identity when the samples are drawn according to the conditional access oracle. We then show that we can learn a succinct representation of a monotone distribution efficiently with a memory constraint on the number of samples that are stored that is almost optimal. We also show that the algorithm for monotone distributions can be extended to a larger class of decomposable distributions.

Cite as

Sampriti Roy and Yadu Vasudev. Testing Properties of Distributions in the Streaming Model. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{roy_et_al:LIPIcs.ISAAC.2023.56,
  author =	{Roy, Sampriti and Vasudev, Yadu},
  title =	{{Testing Properties of Distributions in the Streaming Model}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{56:1--56:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.56},
  URN =		{urn:nbn:de:0030-drops-193588},
  doi =		{10.4230/LIPIcs.ISAAC.2023.56},
  annote =	{Keywords: Property testing, distribution testing, streaming}
}

Search Results

Documents authored by Roy, Sampriti

Testing Properties of Distributions in the Streaming Model

Abstract

Cite as

Thanks for your feedback!

Could not send message